# Copyright (c) 2021 Red Hat, Inc. All rights reserved. This copyrighted
# material is made available to anyone wishing to use, modify, copy, or
# redistribute it subject to the terms and conditions of the GNU General Public
# License v.2 or later.
#
# This program is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
# details.
#
# You should have received a copy of the GNU General Public License along with
# this program; if not, write to the Free Software Foundation, Inc., 51
# Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
"""KPET host condition expression."""
from kpet import boolfunc


class Invalid(Exception):
    """A host condition expression is invalid."""


def validate(condition):
    """
    Check that a host condition expression is valid.

    I.e. it is either:

    * a string starting with "T:", followed by a path to a file with Jinja2
      template rendering to host requirements;
    * a string starting with "H:", followed by an FQDN of a host;
    * a list of expressions, combined with "and" operator (the default),
      or with "or" operator (if the list is the value for "or" key in a
      dictionary)
    * a dictionary of string keys and expression values, where each key
      can be one of the following:
        * "and" - the expression values contained in a dictionary or a
          list value should be combined using the "and" operator (no
          effect on other values);
        * "or" - the expression values contained in a dictionary or a list
          value should be combined using the "or" operator (no effect on
          other values);
        * "not" - the expression value should be negated;

    Args:
        condition:  The condition expression to check.

    Returns:
        The validated condition expression.

    Raises:
        An Invalid exception describing the issue with the expression,
        if it's invalid.
    """
    if isinstance(condition, str):
        if condition[:2] not in ("T:", "H:"):
            raise Invalid(f"Invalid string condition {condition!r}")
    elif isinstance(condition, list):
        for i, sub_condition in enumerate(condition):
            try:
                validate(sub_condition)
            except Invalid as err:
                raise Invalid(
                    f"List item #{i} is invalid"
                ) from err
    elif isinstance(condition, dict):
        for key, sub_condition in condition.items():
            if key not in ("not", "and", "or"):
                raise Invalid(f"Invalid key {key!r}")
            try:
                validate(sub_condition)
            except Invalid as err:
                raise Invalid(
                    f"Expression with key {key!r} is invalid"
                ) from err
    else:
        raise Invalid(
            f"Invalid expression type {type(condition).__name__!r}"
        )
    return condition


def is_valid(condition):
    """
    Check that a host condition expression is valid.

    See validate() for details.

    Args:
        condition:  The host condition expression to check.

    Returns:
        True if the host condition expression is valid, False otherwise.
    """
    try:
        validate(condition)
    except Invalid:
        return False
    return True


def get_strings(condition):
    """
    Get the set of all string conditions (variables) from a condition.

    Args:
        condition:  The condition to retrieve the strings from.

    Returns:
        The set of string conditions from the condition.
    """
    assert is_valid(condition)
    strings = set()
    if isinstance(condition, str):
        strings.add(condition)
    else:
        assert isinstance(condition, (list, dict))
        for subcondition in \
                condition.values() if isinstance(condition, dict) \
                else condition:
            strings |= get_strings(subcondition)
    return strings


def _compile_text(condition, string_bits, and_op=True):
    """
    Compile a condition into the text of a Python expression.

    Compile a condition into the text of a Python expression expecting the
    condition's input in a bitmap variable called "bitmap" with string
    subcondition (variable) values in specified bits, and evaluating to a
    zero/non-zero integer.

    Do not validate arguments for performance.

    Args:
        condition:      The condition to compile.
        string_bits:    A dictionary of (at least) all string subconditions
                        (variables) in the condition and positions of their
                        bits (non-negative integers) in the function's input
                        bitmap.
        and_op:         True if the container condition's elements should be
                        combined using the AND operation. False, if they
                        should be combined using the OR operation. No effect
                        on string conditions.

    Returns:
        The text of the Python expression evaluating the condition, or None,
        if the condition had no string subconditions (variables).
    """
    if isinstance(condition, str):
        return f"(bitmap & {1 << string_bits[condition]})"
    if isinstance(condition, list):
        terms = tuple(_compile_text(sc, string_bits) for sc in condition)
    else:
        def negate(term):
            return None if term is None else f"(not {term})"
        terms = tuple(
            negate(_compile_text(sc, string_bits)) if k == "not" else
            _compile_text(sc, string_bits, and_op=k == "and")
            for k, sc in condition.items()
        )
    terms = tuple(filter(None, terms))
    if not terms:
        return None
    return "(" + (" and " if and_op else " or ").join(terms) + ")"


def _compile_function(condition, string_bits):
    """
    Compile a condition into a function.

    Compile a condition into a function accepting values of all string
    subconditions (variables) as a bitmap and returning the result of
    evaluation. Do not validate arguments for improved performance.

    Args:
        condition:      The condition to compile.
        string_bits:    A dictionary of all string subconditions (variables)
                        in the condition and positions of their bits
                        (non-negative integers) in the function's input
                        bitmap.

    Returns:
        The function evaluating the condition using a bitmap input, or None,
        if the condition had no string subconditions (variables).
    """
    text = _compile_text(condition, string_bits)
    if text is None:
        return None
    code = compile(text, "<string>", "eval", dont_inherit=True)
    # We know what we're doing, pylint: disable=eval-used
    return lambda bitmap: bool(eval(code, {'bitmap': bitmap}))


def evaluate_all(condition, strings):
    """
    Evaluate a condition for all possible inputs.

    Evaluate a condition for all possible inputs, producing a list of outputs
    indexed by input bitmaps (a truth table).

    Args:
        condition:  The condition to evaluate.
        strings:    A list of all string subconditions (variables) in the
                    condition, specifying the order of bits in the bitmaps
                    used to index the resulting outputs. Each string can
                    appear only once in the list.

    Returns:
        The list of condition outputs indexed by input bitmaps, with bit order
        specified by the strings argument.
    """
    assert is_valid(condition)
    assert isinstance(strings, list)
    assert all(isinstance(s, str) for s in strings)
    assert len(strings) == len(set(strings))
    assert get_strings(condition) <= set(strings)
    function = _compile_function(condition,
                                 {s: i for i, s in enumerate(strings)})
    return [function(i) for i in range(0, 1 << len(strings))]


def _from_minterm(strings, minterm):
    """
    Create a condition from a minterm, without validation.

    Create a condition from a list of string conditions and a boolean function
    minterm (see kpet.boolfunc). Do not validate arguments for improved
    performance.

    Args:
        strings:    A list of all string subconditions (variables) in the
                    condition, specifying the order of bits in the minterm.
                    Each string can appear only once in the list.
        minterm:    A tuple containing two bitmaps specifying as-is, and
                    negated minterm's member variables respectively. See
                    kpet.boolfunc for details.

    Returns:
        The created host condition expression.
    """
    terms = []
    for i, string in enumerate(strings):
        if minterm[0] & (1 << i):
            terms.append(string)
        elif not minterm[1] & (1 << i):
            terms.append({"not": string})
    return terms[0] if len(terms) == 1 else terms


def from_minterm(strings, minterm):
    """
    Create a condition from a minterm.

    Create a condition from a list of string conditions and a boolean function
    minterm (see kpet.boolfunc).

    Args:
        strings:    A list of all string subconditions (variables) in the
                    condition, specifying the order of bits in the minterm.
                    Each string can appear only once in the list.
        minterm:    A tuple containing two bitmaps specifying as-is, and
                    negated minterm's member variables respectively. See
                    kpet.boolfunc for details.

    Returns:
        The created host condition expression.
    """
    assert isinstance(strings, list)
    assert all(isinstance(s, str) for s in strings)
    # A list of string conditions is a valid condition
    assert is_valid(strings)
    assert isinstance(minterm, tuple)
    assert len(minterm) == 2
    assert isinstance(minterm[0], int)
    assert isinstance(minterm[1], int)
    condition = _from_minterm(strings, minterm)
    assert is_valid(condition)
    return condition


def _from_minterms(strings, minterms):
    """
    Create a condition from minterms, without validation.

    Create a condition from a list of string conditions and a list of boolean
    function minterms representing a sum-of-products (see kpet.boolfunc). Do
    not validate arguments for improved performance.

    Args:
        strings:    A list of all string subconditions (variables) in the
                    condition, specifying the order of bits in the minterm.
                    Each string can appear only once in the list.
        minterms:   A list of tuples, each containing two bitmaps specifying
                    as-is, and negated minterm's member variables
                    respectively, representing a sum-of-products.
                    See kpet.boolfunc for details.

    Returns:
        The created host condition expression.
    """
    terms = [_from_minterm(strings, minterm) for minterm in minterms]
    if len(terms) == 0:
        return terms
    if len(terms) == 1:
        return terms[0]
    return {"or": terms}


def from_minterms(strings, minterms):
    """
    Create a condition from minterms.

    Create a condition from a list of string conditions and a list of boolean
    function minterms representing a sum-of-products (see kpet.boolfunc).

    Args:
        strings:    A list of all string subconditions (variables) in the
                    condition, specifying the order of bits in the minterm.
                    Each string can appear only once in the list.
        minterms:   A list of tuples, each containing two bitmaps specifying
                    as-is, and negated minterm's member variables
                    respectively, representing a sum-of-products.
                    See kpet.boolfunc for details.

    Returns:
        The created host condition expression.
    """
    assert isinstance(strings, list)
    assert all(isinstance(s, str) for s in strings)
    # A list of string conditions is a valid condition
    assert is_valid(strings)
    assert isinstance(minterms, list)
    assert all(isinstance(m, tuple) and
               isinstance(m[0], int) and isinstance(m[1], int)
               for m in minterms)
    condition = _from_minterms(strings, minterms)
    assert is_valid(condition)
    return condition


def _from_factored_minterms(strings, minterms):
    """
    Create a condition from factored minterms, without validation.

    Create a condition from a list of string conditions and a list of boolean
    function minterms representing a sum-of-products (see kpet.boolfunc),
    with common terms factored out. Do not validate arguments for improved
    performance.

    Args:
        strings:    A list of all string subconditions (variables) in the
                    condition, specifying the order of bits in the minterm.
                    Each string can appear only once in the list.
        minterms:   A list of tuples, each containing two bitmaps specifying
                    as-is, and negated minterm's member variables
                    respectively, representing a sum-of-products.
                    See kpet.boolfunc for details.

    Returns:
        The created host condition expression.
    """
    if len(minterms) == 0:
        return []
    mask = (1 << len(strings)) - 1
    # Find the common minterm
    common = [mask, 0]
    for minterm in minterms:
        common[0] &= minterm[0]
        common[1] |= minterm[0] | minterm[1]
    common = (common[0], (common[0] ^ mask) & common[1])
    # Remove the common minterm from all minterms
    noncommon_positive = mask ^ common[0]
    noncommon_negative = mask ^ ~(common[0] | common[1])
    filtered = []
    for minterm in minterms:
        positive = minterm[0] & noncommon_positive
        negative = ~(minterm[0] | minterm[1]) & noncommon_negative
        first = positive
        second = ~(positive | negative)
        if (first & mask) | (second ^ mask):
            filtered.append((first, second))
    # If common minterm is not empty
    if (common[0] & mask) | (common[1] ^ mask):
        # If any minterms remained
        if filtered:
            condition = _from_minterm(strings, common)
            if not isinstance(condition, list):
                condition = [condition]
            condition.append(_from_minterms(strings, filtered))
        # Else no minterms remained
        else:
            condition = _from_minterm(strings, common)
    # Else common minterm is empty
    else:
        condition = _from_minterms(strings, filtered)
    return condition


def from_factored_minterms(strings, minterms):
    """
    Create a condition from factored minterms.

    Create a condition from a list of string conditions and a list of boolean
    function minterms representing a sum-of-products (see kpet.boolfunc),
    with common terms factored out.

    Args:
        strings:    A list of all string subconditions (variables) in the
                    condition, specifying the order of bits in the minterm.
                    Each string can appear only once in the list.
        minterms:   A list of tuples, each containing two bitmaps specifying
                    as-is, and negated minterm's member variables
                    respectively, representing a sum-of-products.
                    See kpet.boolfunc for details.

    Returns:
        The created host condition expression.
    """
    assert isinstance(strings, list)
    assert all(isinstance(s, str) for s in strings)
    # A list of string conditions is a valid condition
    assert is_valid(strings)
    assert isinstance(minterms, list)
    assert all(isinstance(m, tuple) and
               isinstance(m[0], int) and isinstance(m[1], int)
               for m in minterms)
    condition = _from_factored_minterms(strings, minterms)
    assert is_valid(condition)
    return condition


def minimize(condition):
    """
    Minimize a condition to a sum-of-products form.

    Args:
        condition:  The condition to minimize.

    Returns:
        The minimized condition.
    """
    assert is_valid(condition)

    # Get all string subconditions (variables)
    strings = list(sorted(get_strings(condition)))

    # If there are no variables
    if not strings:
        # Return an empty condition, which will always match
        return []
    # Build the truth table (list of function values)
    values = evaluate_all(condition, strings)
    # Minimize the expression described by the truth table
    _, minexpr = boolfunc.minimize(len(strings),
                                   [i for i, v in enumerate(values) if v],
                                   [])
    # If the minimized expression is always True
    if minexpr is True:
        # Return an empty condition, which will always match
        return []
    # If the minimized expression is always False
    if minexpr is False:
        # Return an empty hostname, which will never match
        return "H:"
    # Otherwise, our expression is a list of minterms
    condition = _from_factored_minterms(strings, minexpr)
    assert is_valid(condition)
    assert evaluate_all(condition, strings) == values
    return condition
